def FindLongestIncreasingSubsequence(A):
    """
    一个数组由多少个子序列？大小为1的子序列为C(n,1)，为2的有C(n,2)，
    所以，全部加起来是 C(n,1)+C(n,2)+...+C(n,n) ，是2^n的级别。
    这个算法如果暴力枚举，就是指数复杂度。现在变成了O(n^2)复杂度已经是改善了。
    我感觉不可能是O(n)，因为子序列有两个端点。看了答案也是 n 平方复杂度。
    """
    maxLength = -1
    solution = None
    # 每个元素开头的子序列都有可能是解。
    for i in range(0, len(A)):
        localMaxLength = 1
        maxElement = A[i]
        localSolution = [maxElement]
        # 逐步向后扩展。
        for j in range(i + 1, len(A)):
            if A[j] > maxElement:
                localMaxLength += 1
                maxElement = A[j]
                localSolution.append(maxElement)

        if localMaxLength > maxLength:
            maxLength = localMaxLength
            solution = localSolution

    print(A)
    print(maxLength)
    print(solution)
    return maxLength, solution


FindLongestIncreasingSubsequence([1, 5, 3, 8, 10, 6, 4, 9]) # 1 5 8 10
FindLongestIncreasingSubsequence([2, 8, 4, -4, 5, 9, 11]) # 2 8 9 11
